#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int sum = 0;
        int ans = 0;
        unordered_map<int, int> dp;
        dp[0] = 1;
        for (int& a : A) {
            if (a < 0) {
                a = K - abs(a) % K;
            }
            sum += a;
            int val = sum % K;
            unordered_map<int, int>::iterator it = dp.find(val);
            if (it != dp.end()) {
                ans += it->second;
                it->second++;
            } else {
                dp[val] = 1;
            }
        }
        return ans;
    }
};